#!/usr/bin/python3.7
# -*- coding: utf-8 -*-
# create by 火苗999℃
import random
from maze import *
from draw_maze import *
#Aldous-Broder algorithm
#The Aldous-Broder algorithm also produces uniform spanning trees.

# 1.Pick a random cell as the current cell and mark it as visited.
# 2.While there are unvisited cells:
#   1.Pick a random neighbour.
#   2.If the chosen neighbour has not been visited:
#       1.Remove the wall between the current cell and the chosen neighbour.
#       2.Mark the chosen neighbour as visited.
#   3.Make the chosen neighbour the current cell.

# Aldous-Broder算法
# Aldous-Broder算法也生成统一的生成树。
# 1。选择一个随机的单元格作为当前单元格，并将其标记为已访问的。
# 2。当存在未访问细胞时:
#   1。随机选择一个邻居。
#   2。如果选中的邻居没有被访问:
#       1。移除当前单元格和所选邻居之间的墙。
#       2。标记被选中的邻居已被拜访过。
#   3。使选择的邻居成为当前单元格。


# 随机格子
def aldous_broder_maze_demo(levels, rows, cols):
    if 0 == levels % 2:
        levels+=1
    if 0 == rows % 2:
        rows+=1
    if 0 == cols % 2:
        cols+=1
    # 初始化全为墙
    maze_map = maze_init_draw(levels, rows, cols)
    # 
    notusegrids = [] # 没有访问过的格子,单数代表格子，双数是墙壁
    for tz in range(0, levels):
        for tx in range(0, cols):
            for ty in range(0, rows):
                if maze_map[tx][ty][tz]==CELL_NO_VISIT:
                    notusegrids.append((tx, ty, tz))
                # 演示用
                elif maze_map[tx][ty][tz] == WALL_NO_VISIT:
                    maze_map[tx][ty][tz] = WALL_VISIT
    # 选择一个随机的单元格作为当前单元格，并将其标记为已访问的。
    nowx,nowy,nowz = random.choice(notusegrids)
    # 标记迷宫
    maze_map[nowx][nowy][nowz]=CELL_VISIT
    notusegrids.remove((nowx,nowy,nowz))
    posx,posy=None,None
    # 当存在未访问细胞时:
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                return
        # 当存在未访问细胞时:
        if  notusegrids:
            directions = []
            # 可随机方向
            if nowy > 1:
                directions.append('f')
            if nowx > 1:
                directions.append('l')
            if nowy < rows-2:
                directions.append('b')
            if nowx < cols-2:
                directions.append('r')
            if nowz < levels-1:
                directions.append('u')
            if nowz > 0:
                directions.append('d')
            if len(directions):
                # 随机一个方向
                move = random.choice(directions)
                # 如果选中的邻居没有被访问:
                    #   1。移除当前单元格和所选邻居之间的墙。
                    #   2。标记被选中的邻居已被拜访过。
                    #   3。使选择的邻居成为当前单元格。
                if move == 'f':
                    newy = nowy-2
                    newx = nowx
                    newz = nowz
                    opwall=(nowx,nowy-1,nowz)
                if move == 'l':
                    newy = nowy
                    newx = nowx-2
                    newz = nowz
                    opwall=(nowx-1,nowy,nowz)
                if move == 'b':
                    newy = nowy+2
                    newx = nowx
                    newz = nowz
                    opwall=(nowx,nowy+1,nowz)
                if move == 'r':
                    newy = nowy
                    newx = nowx+2
                    newz = nowz
                    opwall=(nowx+1,nowy,nowz)
                if move == 'u':
                    newy = nowy
                    newx = nowx
                    newz = nowz+2
                    opwall=(nowx,nowy,nowz+1)
                if move == 'd':
                    newy = nowy
                    newx = nowx
                    newz = nowz-2
                    opwall=(nowx,nowy,nowz-1)
                # 如果选中的邻居没有被访问:
                if maze_map[newx][newy][newz] == CELL_NO_VISIT:
                    #   1。移除当前单元格和所选邻居之间的墙。
                    if opwall:
                        maze_map[opwall[0]][opwall[1]][opwall[2]] = NOWALL
                    #   2。标记被选中的邻居已被拜访过。
                    if move == 'd':
                        if maze_map[nowx][nowy][nowz] == STAIRS_U:
                            maze_map[nowx][nowy][nowz]=STAIRS_UD
                        else:
                            maze_map[nowx][nowy][nowz]=STAIRS_D
                        maze_map[newx][newy][newz]=STAIRS_U
                    elif move == 'u':
                        if maze_map[nowx][nowy][nowz] == STAIRS_D:
                            maze_map[nowx][nowy][nowz]=STAIRS_UD
                        else:
                            maze_map[nowx][nowy][nowz]=STAIRS_U
                        maze_map[newx][newy][newz]=STAIRS_D
                    else:
                        maze_map[newx][newy][newz]=CELL_VISIT
                    #   3。使选择的邻居成为当前单元格。
                    nowx=newx
                    nowy=newy
                    nowz=newz
                    notusegrids.remove((newx,newy,newz))
                else:
                    # 使选择的邻居成为当前单元格。
                    nowx=newx
                    nowy=newy
                    nowz=newz
        # 画
        draw_maze(maze_map, levels, rows, cols, (nowx, nowy, nowz), not notusegrids)
        time_passed = clock.tick(30)
        pygame.display.update()
    return


# main
if __name__ == "__main__":
    '''main'''
    aldous_broder_maze_demo(4, 11, 15)
